Keeping data private is important to many enterprises as well as individuals. As a result, more and more data are encrypted for storage and/or transmission.
However, there are many situations such as keyword matching where it is desirable for a third party to be able to perform some action with the text associated with an encrypted record, document or message. An example is when one user wants a server to process emails or other messages containing the word “urgent” from another user in some non-standard way. The data is encrypted by the sender with one key, which the sender does not want made public, before being transmitted to the server. The recipient only wants to provide a query with an encrypted keyword set (e.g., containing the word “urgent”) to the server, without providing his or her secret key to the server. Because the data is encrypted with one key and the keyword set with another, the server cannot match the two encrypted sets of data, and can only match by decrypting both before comparing; however the server does not have the keys to decrypt.
More formally, the problem may be stated as follows. Let X={X1, X2, X3 . . . } and Y={Y1, Y2, Y3 . . . } be sets of encrypted words, where each set is encrypted with a distinct secret key. It is desirable to have a decision maker be able to decide if Xj and Yi are encryptions of the same cleartext word, without using any secret, such that the decision maker is not be able to (efficiently) compute the cleartext.